package leetCode;

import java.util.ArrayDeque;

public class Q143 {
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    public void reorderList(ListNode head) {
        ArrayDeque<ListNode> deque = new ArrayDeque<>();

        for(ListNode cur = head.next;cur!=null;cur = cur.next){
            deque.add(cur);
        }

        while (!deque.isEmpty()){
            if(deque.size()>1) {
                ListNode listNode = deque.removeLast();
                head.next = listNode;
                head = head.next;
            }else {
                ListNode listNode = deque.removeLast();
                head.next = listNode;
                head = head.next;
                head.next = null;
            }

            if (!deque.isEmpty()) {
                if(deque.size()>1){
                    ListNode listNode1 = deque.removeFirst();
                    head.next = listNode1;
                    head = head.next;
                }else {
                    ListNode listNode1 = deque.removeFirst();
                    head.next = listNode1;
                    head = head.next;
                    head.next = null;
                }
            }
        }

    }
}
